package leetcode.D200.T152;

/**
 * @Author: DYZ
 * @Create: 2022-04-16 11:46:58
 */
class Solution {
    /**
     * 动态规划
     *  如果是求累加和最大子数组，就需要用dp[i]记录以nums[i]结尾的子数组的最大和
     *  但是求乘积最大子数组，既需要记录最大乘积，也需要记录最小乘积，因为**负负得正**
     */
    public int maxProduct(int[] nums) {
        int dp1 = nums[0], dp2 = nums[0];
        int result = nums[0];
        for (int i=1; i<nums.length; ++i) {
            int temp = dp1;
            dp1 = Math.max(nums[i], Math.max(nums[i] * dp1, nums[i] * dp2));
            dp2 = Math.min(nums[i], Math.min(nums[i] * temp, nums[i] * dp2));
            result = Math.max(dp1, result);
        }
        return result;
    }
}
